package com.rising.face.ali.bishi.mergelist;

import java.util.List;

/**
 * @Author: rising
 * @Description:
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 * @Date: create in 2021/2/28 17:17
 */
public class MergeList {
    public static void main(String[] args) {
        String str1 = "1->2->4->5->6->6";
        String str2 = "1->3->4->7";
        ListNode listNode1 = generateList(str1);
        ListNode listNode2 = generateList(str2);
        System.out.println("两个链表如下：");
        printList(listNode1);
        printList(listNode2);

        System.out.println("合并后的链表如下");
        ListNode mergeListNode = mergeTwoLists(listNode1, listNode2);
        printList(mergeListNode);
    }

    public static void printList(ListNode listNode) {
        while (listNode.next != null) {
            System.out.print(listNode.val + "->");
            listNode = listNode.next;
        }
        System.out.println(listNode.val);
    }

    public static ListNode generateList(String str) {
        String[] splits = str.split("->");
        ListNode rtnlistNode = null;
        for (int i = splits.length - 1; i >= 0; i--) {
            ListNode listNode = new ListNode(Integer.valueOf(splits[i]));
            if (rtnlistNode == null) {
                rtnlistNode = listNode;
            } else {
                listNode.next = rtnlistNode;
                rtnlistNode = listNode;
            }
        }
        return rtnlistNode;
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

}
